package tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 二叉树的中序遍历94 {

    //    public List<Integer> inorderTraversal(TreeNode root) {
//        if (root==null){
//            return null;
//        }
//
//        inorderTraversal(root.left);
//
//        inorderTraversal(root.right);
//    }
    // 1.递归
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        inorder(root, list);
//        return list;
//    }
//
//    private void inorder(TreeNode root, List<Integer> list) {
//        if (root == null) {
//            return;
//        }
//
//        inorder(root.left, list);
//        list.add(root.val);
//        inorder(root.right, list);
//    }

    // 2.迭代
    // 方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，
    // 区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        // Deque
        Deque<TreeNode> stk = new LinkedList<>();
        // 不为空继续迭代
        while (root != null || !stk.isEmpty()) {
            while (root != null) {
                stk.push(root);
                root = root.left;
            }
            root = stk.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}
